template<typename _Ty>
struct LeftistTree {

    struct Node {
        _Ty key;
        int root, p, left, right, dist;

        Node() {
            key = root = p = left = right = dist = 0;
        }
    };

    std::vector<Node> Tree;

    LeftistTree() {};

    // v(n + 1)
    LeftistTree(std::vector<_Ty> v) {
        init(v);
    }

    void init(std::vector<_Ty> v) {
        Tree.resize(v.size());
        Tree[0].dist = -1;
        for (int i = 1; i < v.size(); i++) {
            Tree[i].key = v[i];
            Tree[i].root = i;
        }
    }

    // query i th node in the tree of i-th node root
    int find(int i) {
        Tree[i].root = (Tree[i].root == i ? i : find(Tree[i].root));
        return Tree[i].root;
    }

    // merge two trees
    int merge(int i, int j) {
        if(i == 0 || j == 0) {
            return i + j;
        }
        // 维护大根堆，如果值一样，编号小的节点做头
        if(Tree[i].key < Tree[j].key || (Tree[i].key == Tree[j].key && i > j)) {
            std::swap(i, j);
        }
        Tree[i].right = merge(Tree[i].right, j);
        Tree[Tree[i].right].p = i;
        if(Tree[Tree[i].left].dist < Tree[Tree[i].right].dist) {
            std::swap(Tree[i].right, Tree[i].left);
        }
        Tree[i].dist = Tree[Tree[i].right].dist + 1;
        Tree[Tree[i].left].root = Tree[Tree[i].right].root = i;
        return i;
    }

    // remove i-th node
    int remove(int i) {
        int h = find(i);
        Tree[Tree[i].left].root = Tree[i].left;
        Tree[Tree[i].right].root = Tree[i].right;
        int s = merge(Tree[i].left, Tree[i].right);
        Tree[s].p = 0;
        Tree[i].dist = Tree[i].left = Tree[i].right = 0;
        if(h == i) {
            Tree[i].root = s;
        } else {
            int f = Tree[i].p;
            if(Tree[f].left == i) {
                Tree[f].left = 0;
            } else {
                Tree[f].right = 0;
            }
            Tree[i].p = 0;
            for(int d = -1; Tree[f].dist > d + 1; f = Tree[f].p, d++) {
                Tree[f].dist = d + 1;
                if(Tree[Tree[f].left].dist < Tree[Tree[f].right].dist) {
                    std::swap(Tree[f].left, Tree[f].right);
                }
            }
            Tree[i].root = merge(h, s);
        }
        return Tree[i].root;
    }

    // before pop please find the i`s root
    int pop(int i) {
        Tree[Tree[i].left].root = Tree[i].left;
        Tree[Tree[i].right].root = Tree[i].right;
        Tree[i].root = merge(Tree[i].left, Tree[i].right);
        Tree[i].dist = Tree[i].left = Tree[i].right = 0;
        return Tree[i].root;
    }

};